package 题目集.贪心;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/two-city-scheduling/description/
 *
 */
public class ch01_两地调度 {
	/**
	 * 因为每个人都需要去a地或者b地。
	 * 那么对于这个人而言，去a或b,是看自己去两地的代价，哪个小。
	 * 对于想去a地而言(ai-bi)是最小的，先对(ai-bi)进行排序升序。
	 */
    public int twoCitySchedCost(int[][] costs) {
    	Arrays.sort(costs,(a1,a2)->{
    		return (a1[0]-a1[1])-(a2[0]-a2[1]);
    	});
    	int sum=0;
    	for(int i=0;i<costs.length/2;i++) {
    		sum+=costs[i][0];
    	}
    	for(int i=costs.length/2;i<costs.length;i++) {
    		sum+=costs[i][1];
    	}
    	return sum;
    }
}
